package com.code.leetcode._202508;

// 63不同路径II
public class UniquePathsWithObstacles {
    /**
     * 给定一个m*n的整数数组grid。一个机器人初始位于左上角(即grid[0][0]),机器人尝试移动到右下角
     * (即grid[m-1][n-1])。机器人每次只能向下或者向右移动一步。
     * 网格种的障碍物和空位置分别用1和0来表示。机器人的移动路径中不能包含任何有障碍物的方格
     * 返回机器人能够到达右下角的不同路径数量
     * 测试用例保证答案小于等于2*10^9
     * 示例1：输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     * 输出：2
     * 解释：3x3 网格的正中间有一个障碍物。
     * 从左上角到右下角一共有 2 条不同的路径：
     * 1. 向右 -> 向右 -> 向下 -> 向下
     * 2. 向下 -> 向下 -> 向右 -> 向右
     * 示例2：输入：obstacleGrid = [[0,1],[0,0]]
     * 输出：1
     **/
    public static void main(String[] args) {
        UniquePathsWithObstacles u = new UniquePathsWithObstacles();
        System.out.println(u.uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
    }

    /**
     * 动态规划
     * 我们用f(i,j)来表示从坐标(0,0)到坐标(i,j)的路径总数，u(i,j)表示坐标(i,j)是否可行。如果坐标(i,j)有障碍物，u(i,j)=0，否则u(i,j)=1
     * 因为 机器人每次只能向下或者向右移动一步，所以从坐标(0,0)到坐标(i,j)的路径总数的值只取决于坐标(0,0)到坐标(i-1,j)的路径总数和从坐标(0,0)
     * 到坐标(i,j-1)的路径总数，即f(i,j)只能通过f(i-1,j)和f(i,j-1)转移得到，当坐标(i,j)本身有障碍的时候，任何路径都到不了f(i,j)，此时f(i,j)=0
     * 下面我们来讨论坐标(i,j)没有障碍的情况；如果坐标(i-1,j)没有障碍，那么就意味着从坐标(i-1,j)可以走到(i,j)，即(i-1,j)位置对(i,j)的贡献为f(i-1,j)
     * 同理，当坐标(i,j-1)没有障碍的时候，(i,j-1)位置对f(i,j)的贡献为f(i,j-1)
     * 很显然我们可以给出一个时间复杂度O(nm)并且空间复杂度也是O(nm)的实现，由于这里f(i,j)只与f(i-1,j)和f(i,j-1)有关，我们可以运用 滚动数组思想
     * 把空间复杂度优化成O(m)
     **/
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }
        return f[m - 1];
    }

}
